package 剑指offer;


import 栈和队列.CalSpan;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-25
 */
public class 合并两个有序的数组 {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 0, 0, 0};
        int[] arr2 = {2, 5, 6};
        merge(arr1, 3, arr2, 3);
        CalSpan.printArr(arr1);

    }

    public static void merge(int[] arr1, int m, int[] arr2, int n) {
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                arr1[i] = arr2[i];
            }
            return;
        }
        if (n == 0) {
            return;
        }
        int i = 0, j = 0;
        int index1 = 0, index2 = 0;
        while (index1 < arr1.length) {
            while (index2 + j < n && arr2[index2 + j] < arr1[index1]) {
                j++;
            }
            //向后移动j位
            if (j > 0) {
                m = m + j;
                for (int k = m - 1; k >= index1 + j; k--) {
                    arr1[k] = arr1[k - j];
                }
                int temp = j;
                while (temp > 0) {
                    temp--;
                    arr1[index1 + temp] = arr2[index2 + temp];
                }
                index1 += j;
                index2 += j;
            } else {
                index1++;
            }
            j = 0;
            while (index1 == m && index2 != n) {
                arr1[index1++] = arr2[index2++];
                m++;
            }
        }
    }
}
